﻿#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)

#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
#include<stdbool.h>
#include<assert.h>
#include<list>
#include<set>
#include<iomanip>
#include<map>
#include<queue>
#include<unordered_map>
#include<deque>
using namespace std;

//void* realloc(void* ptr, size_t new_size);
//
//result = (condition) ? num1 : num2;
//
////简单条件赋值
//
//int maxs = (a > b) ? a : b;
//
////函数返回值优化
//
//std::string getstatus(bool rescure) {
//	return rescure ? "Success" : "Failure";
//}
//
////初始化常量或引用
//
//const int& ref = (x > 0) ? x : y;
//
////模板或宏中的引用
//
//#define MIN(a,b)((a)<(b)?(a):(b));
//
////避免副作用
////错误示例
//
//int i = 0;
//(i == 0) ? i++ : i--;
//
////类型转换
//
//double d = (true) ? 5 : 3.14;
//char* p = (flag) ? "hello" : nullptr;
//
///*注意：int*和double不兼容*/
//

//#include<iostream>
//
//using namespace std;
//
//const int N = 105;
//
//int a[N][N], b[N][N], c[N][N];
//
//int main() {
//	int n, m, k; cin >> n >> m >> k;
//	for (int i = 1; i <= n; ++i) {
//		for (int j = 1; j <= m; ++j) {
//			cin >> a[i][j];
//		}
//	}
//	for (int i = 1; i <= m; ++i) {
//		for (int j = 1; j <= k; ++j) {
//			cin >> b[i][j];
//		}
//	}
//	for (int i = 1; i <= n; ++i) {
//		for (int j = 1; j <= k; ++j) {
//			for (int t = 1; i <= m; ++t) {
//				c[i][j] += a[i][k] * b[k][j];
//			}
//			cout << c[i][j] << endl;
//		}
//	}
//	return 0;
//}

//int main() {
//	int a, b; cin >> a >> b;
//	double c,d,e;
//	c = a / b;
//	d = (a + b - 1) / b;
//	e = (a - 1) / (b + 1);
//	cout << c << " " << d << " " << e << " " << endl;
//	return 0;
//}


//int main() {
//	int a = 12, b = 5;
//	if (a | b && -a | b) cout << "y" << endl;
//	else cout << "n" << endl;
//	return 0;
//}

//#include <iostream>
//#include <tuple> // 用于返回多个值
//using namespace std;
//
//// 判断同余：a ≡ b (mod m)
//bool isCongruent(int a, int b, int m) {
//    return (a - b) % m == 0;
//}
//
//// 扩展欧几里得算法（求ax + by = gcd(a,b)）
//tuple<int, int, int> extendedGCD(int a, int b) {
//    if (b == 0) return { a, 1, 0 };
//    auto [gcd, x1, y1] = extendedGCD(b, a % b);
//    int x = y1;
//    int y = x1 - (a / b) * y1;
//    return { gcd, x, y };
//}
//
//// 求模逆元（a⁻¹ mod m，要求a与m互质）
//int modInverse(int a, int m) {
//    auto [gcd, x, y] = extendedGCD(a, m);
//    if (gcd != 1) {
//        throw invalid_argument("逆元不存在");
//    }
//    return (x % m + m) % m; // 确保结果为正
//}
//
//// 解线性同余方程 ax ≡ b (mod m)
//pair<bool, int> solveCongruence(int a, int b, int m) {
//    auto [gcd, x, y] = extendedGCD(a, m);
//    if (b % gcd != 0) return { false, 0 };
//
//    int x0 = (x * (b / gcd)) % m;
//    x0 = (x0 + m) % m; // 最小正整数解
//    return { true, x0 };
//}
//
//// 中国剩余定理（解同余方程组）
//int chineseRemainder(const vector<pair<int, int>>& congruences) {
//    int result = 0;
//    int product = 1;
//
//    // 计算所有模数的乘积
//    for (auto& [rem, mod] : congruences) {
//        product *= mod;
//    }
//
//    for (auto& [rem, mod] : congruences) {
//        int Mi = product / mod;
//        auto [gcd, inv, _] = extendedGCD(Mi, mod);
//        result += rem * Mi * inv;
//    }
//
//    return result % product;
//}
//
//int main() {
//    // 示例1：判断同余
//    cout << "7 ≡ 22 (mod 5)? " << boolalpha
//        << isCongruent(7, 22, 5) << endl; // true
//
//    // 示例2：求逆元
//    try {
//        cout << "3⁻¹ mod 7 = " << modInverse(3, 7) << endl; // 5
//    }
//    catch (const exception& e) {
//        cerr << e.what() << endl;
//    }
//
//    // 示例3：解方程 3x ≡ 4 (mod 7)
//    auto [hasSolution, x] = solveCongruence(3, 4, 7);
//    if (hasSolution) {
//        cout << "解为 x ≡ " << x << " mod 7" << endl; // 6
//    }
//
//    // 示例4：中国剩余定理
//    vector<pair<int, int>> equations = {
//        {2, 3},  // x ≡ 2 mod 3
//        {3, 5},  // x ≡ 3 mod 5
//        {2, 7}   // x ≡ 2 mod 7
//    };
//    cout << "最小解: " << chineseRemainder(equations) << endl; // 23
//
//    return 0;
//}

//int gcd(int a, int b) {
//	return b == 0 ? a : gcd(b, a % b);
//}
//
//int main() {
//	int a, b; cin >> a >> b;
//	gcd(a, b);
//	cout << gcd(a,b)<< endl; 
//	return 0;
//}

//bool check(int a, int b, int m) {
//	return (a % m == b % m);
//}
//
//int main() {
//	cout << check(15, 5, 33) << endl;
//	return 0;
//}

//int check(int a, int b, int m) {
//	a %= m;
//	b %= m;
//	for (int x : m) {
//		if ((a * x) % m == b) return x;
//	}
//	return -1;
//}
//
//int main() {
//	cout << check(2, 3, 5) << endl;
//	return 0;
//}

//int main() {
//	int a, b; cin >> a >> b;
//	double c,d,e;
//	c = a / b;
//	d = (a + b - 1) / b;
//	e = (a - 1) / (b + 1);
//	cout << c << " " << d << " " << e << " " << endl;
//	return 0;
//}

//#include<iostream>
//#include<algorithm>
//#include<vector>
//using namespace std;
//
//const int MOD = 1e9 + 7;
//const int N = 1e8 + 9;
//
//int t[N];
//int a[N];
//int b[N];
//int c[N];
//
//int gcd(int a, int b) {
//	return b == 0 ? a : gcd(b, a % b);
//}
//
//int main() {
//	int n, k; cin >> n >> k;
//	if (n >= 2 && n <= 10) {
//		while (k--) {
//			for (int i = 1; i <= n; ++i) {
//				for (int j = 1; j <= n; ++j) {
//					cin >> t[i];
//				}
//			}
//
//			for (int k = 1; k <= n; ++k) {
//				for (int j = 1; j <= n; ++j)【
//					c[i][j] = a[i][k] * n[k][j];
//			}
//
//
//		}
//	}
//}

//bool qusert_sqrt(double x, float y, int z) {
//	return sqrt(x), sqrt(y), sqrt(z);
//}
//
//int main() {
//	double x = 2.5;
//	float y = 4.0;
//	int z = 3;
//	cout << qusert_sqrt(x, y, z) << endl;
//	return 0;
//}

//d = sqrt((x1 - x2) ^ 2 - (y1 - y2) ^ 2);

//int dist(int x1, int x2, int y1, int y2) {
//	int dx = abs(x1 - x2), dy = abs(y1 - y2);
//	return dx + dy;
//}
//
//int main() {
//	int x1 = 2, x2 = 3, y1 = 4, y2 = 1;
//	cout << dist(x1, x2, y1, y2) << endl;
//	return 0;
//}

//int main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	double x, y, r; cin >> x >> y >> r;
//	double pi = acos(-1);
//	double C = 2 * pi * r;
//	double S = pi * r * r;
//	cout << C << " " << S << endl;
//	return 0;
//}

